n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
def knapSack(n,c,w,v):
    dp=[[0 for _ in range(c+1)] for _ in range(n)]
    #先处理第一行的情况
    for i in range(c):
        if i>=w[0]:
            dp[0][i+1]=v[0]
    #处理剩余行
    for i in range(1,n):
        for j in range(c+1):
            if j==0:
                dp[i][j]=0
            #先将第i-1行的值赋值给i行
            dp[i][j]=dp[i-1][j]
            if j>=w[i]:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    print(dp)


#正确
def knapSack1(n,c,w,v):
    #创建状态转移矩阵
    dp=[[0 for _ in range(c+1)] for _ in range(n)]
    #先处理第一行
    for i in range(c+1):
        #当容量为0的时候，应该为0
        if i==0:
            dp[0][i]=0
        if i<w[0] and i>0:
            dp[0][i]=0
        if i>=w[0]:
            dp[0][i]=v[0]
    # print(dp)
    #处理剩余行
    for i in range(1,n):
        for j in range(c+1):
            dp[i][j]=dp[i-1][j]
            if j>=w[i]:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    print(dp)
knapSack1(n,c,w,v)